/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2021-12-11
 * Time: 21:37
 */
public class Solution {
    public void getNext(int[] next,String needle){
        next[0]=-1;
        next[1]=0;
        int j=2;
        int k=0;
        while(j<needle.length()){
            if((k==-1) || needle.charAt(j-1)==needle.charAt(k)){
                next[j]=k+1;
                j++;
                k++;
            }else{
                k=next[k];
            }
        }
    }
    public int strStr(String haystack, String needle) {
        int lenh=haystack.length();
        int lenn=needle.length();
        if (lenn == 0) {
            return 0;
        }
        if (lenh == 0) {
            return -1;
        }
        int[] next=new int[lenn+1];
        getNext(next,needle);
        int i=0;
        int j=0;
        while(i<lenh && j<lenn){
            if(j==-1 || (haystack.charAt(i)==needle.charAt(j))){
                i++;
                j++;
            }else{
                j=next[j];
            }
        }
        if(j>=lenn){
            return i-j;
        }else{
            return -1;
        }
    }
}
